What's the cost of find, insert, and remove on a BST?



What characteristic of the tree affects this cost?

	cost is proportional to the height of the tree


What's the height of a BST with N nodes?

	it depends
	best, worst, and average cases must be analyzed


What's the best-case height of a BST with N nodes?

	the tree is perfectly balanced
	the height is O(log N)
	the cost of find, insert, and remove is O(log N)


What's the worst-case height of a BST with N nodes?

	the tree is like a linked list
	the height is O(N)
	the cost of find, insert, and remove is O(N)


What's the average-case height of a BST with N nodes?

	assume random insertion sequence
	average of all insertion orders
	the average case is 38% worse than the best case
	the height is still O(log N)
	the cost of find, insert, and remove is O(log N)


What happens if you insert a sorted sequence of items into a BST?

	causes worst-case behavior
	need to keep tree balanced